package problem139;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

//139.单词差分
//https://leetcode.cn/problems/word-break/

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        s = " " + s;
        int n = s.length();
        Set<String> set = new HashSet<>();
        for(String word:wordDict) {
            set.add(word);
        }
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for(int i = 1; i<n; i++) {
            int j = i;
            while(j > 0 ) {
                if(set.contains(s.substring(j,i+1))) {
                    dp[i] = dp[j-1];
                    if(dp[i]) break;
                }
                j--;
            }
        }
        return dp[n-1];
    }
}

/*
dp[i]:以第i个字母为结尾,能否用字典中的单词拼接
*/